The basic advantage of the new high bandwidth, low delay, fixed length cell based transfer mode techniques, such as Asynchronous Transfer Mode (ATM), is to allow multiplexing and switching of different types of information over the same network: data, voice, image, video, while optimizing the bandwidth and resources utilization.
To that end, the various network user's traffic are split into fixed and/or variable length data packets (or blocks) which are then split into fixed length cells in an ATM type network. The basic problem is to conveniently orient these cells within the network bearing in mind that thousands of users connected to the same network shall share the same network link. In a high speed transmission environment, and with users operating essentially in burst mode and at different speed from one another, one may easily understand that conflicts and congestions can occur within the network.
Congestion control inside these networks is one of the major problems to be resolved. As the cells are short, no space is allocated in their headers to enable error recovery for the cell payload (i.e. users data). If one cell of the block has been lost or discarded by the network in case of network congestion, error recovery is performed at the higher-level by recovery protocols retransmitting the user data block. The error rate being extremely low in the internode links, cells lost because of random errors is not a potential problem. However, when a node discards cells for reason of traffic congestion, it is unlikely that these cells will come from a small number of logical data blocks. Discarding 1000 cells, if the average user data blocks length is 2KBytes (a low estimate), sent as 43 cells, may cause the network to absorb a retransmission of 43,000 cells! This case indeed is the worse case when the 1000 messages come from 1000 different connections. That is why the protocols need to be efficient enough to minimize congestion problems in this type of networks.
In the ATM connection-oriented networks, the end-to-end traffic of data for one user, between the source and the destination, is represented by a Virtual Connection (VC); several Virtual Connections may be grouped in a Virtual Path (VP) that can be switched as a unit. The bandwidth is allocated dynamically, based on predefined conditions and agreements with each user, as part of a connection setup signalling procedure that precedes end-to-end information exchange. At call admission time, the source user provides, in addition to the destination point, a set of parameters, called the traffic descriptors, which attempt to describe the traffic that will be generated onto the links. For instance, a mandatory descriptor is the peak cell rate of the connection, R. If this parameter is sufficient to fully describe Constant Bit Rate (CBR) connections, i.e., periodic stream of cells such as uncompressed voice, further parameters are necessary to describe Variable Bit Rate (VBR) connections such as those for video traffic. The burst of traffic is measured by the average cell rate and the average duration of an emission at the peak rate R in most of the high speed networks literature. As indicated above, in ATM networks, cells may be lost or unacceptable delays can be induced in case of traffic congestion. Depending on the type of traffic conveyed over the ATM network, the first or the second just mentioned behavior of the network, in case of congestion, may damage the quality of traffic over the virtual connections: for voice traffic, cells can be lost but a delay in transmission is unacceptable. When pure data is transferred on the virtual connection, the delay can be acceptable but not the cell loss. That's why the network guarantees a Quality of Service (QoS). The QoS guaranteed by a network is, in most cases, expressed in terms of cell loss probability and maximum end-to-end delay for a cell, independently of network topologies and protocols. One can note that the end-to-end delay between two users is increased if the end-to-end connection crosses different network entities (private or public carrier networks) which have their own protocols and traffic management.
In order to meet the QoS, the network nodes have to control the traffic congestion both at connection admission time and once the connection is established.
At connection admission time the access node has to decide if it can accept the connection or not: its decision is based on the actual load of the links, and its analyzis of the traffic parameters of the connection. Moreover, it has also to compute a path table to carry this overload of traffic through the different nodes. If no path is found, the call is rejected. It is important to note that the decision to accept a new call has to be taken not only if the network node estimates that the QoS for the connection will be met but also if it is sure that the added traffic will not have a significant impact on the QoS of all the connections already established.
A first control on traffic congestion, once the connection is established, is performed by the policing function implemented in a device, the policer, of the network access node adapter. The policer will detect and penalize the violation of the peak cell rate on the current traffic compared to the one required at call set up.
Instead of the peak cell rate, another descriptor the Sustainable Cell Rate, (SCR) can be used as a criterion for the policing function. Accordingly, any reference to the peak cell rate can be replaced by SCR. The policing function is also referred to, in the ATM literature, as the Network Parameter Control (NPC) or the Usage Parameter Control (UPC) depending on whether the source unit is a Network Node or a Customer Premise Node (or port). Indeed, an efficient policing function should be transparent as long as the traffic characteristics provided by the source at call setup are met. This means that the policing algorithm should discard or tag as discardeable, user cells unless the cell loss probability is less than or equal to the one defined by the QoS. On the other hand, the policing function will also discard or tag the cells that are in excess versus the peak cell rate provided at call set up.
A second control of traffic congestion consists in shaping the output network node traffic by spacing the cells departures in such a way that the time between two departures of cells for the same connection shall never be below the minimal value negotiated at connection setup time. It has been shown that, on the average, the multiplexing of spaced cells tends to decrease the `burstiness` of the aggregate traffic and then allows a better utilization of the network resources. This invention shall essentially focus on this second aspect of traffic congestion, and accordingly shall be implemented within (or combined with) the shaping device (shaper).
FIG. 1 shows the shaping principle applied to the input cells stream 1. The shaded cells have been sent by a first user and the cells marked with a cross have been sent by a second user. The result of shaping is shown with the output cells stream 2: the cells marked with = have been moved and the departure time between two cells has become more regular. The spacing of the cells is done according to the bandwidth sharing required by the users: in the output cell stream, the departure time between two cells is smaller for the cells of the first user than for the second user's cells, because the first user has required a greater bandwidth share than the second user. Moreover, in the output stream the bursts of traffic have decreased: one can note that the groups of two cells belonging to the same connection of the input stream 1 have disappeared in the output stream 2.
The policing function is implemented in the access network nodes. The device implementing the policing function, the policer, is part of the high speed adapter cards; it controls and, if necessary, penalizes the traffic entering the network.
The shaping function is implemented in the devices accessing a network: they can be Customer Premise Nodes accessing an ATM network or a Network Node at the boundary of a first ATM network and intending to access another ATM network. As some Customer Premise Nodes can implement a policer, it is recommended to implement also the shaping function in the node at the boundary of a network connecting Customer Premise Nodes with policers. The device implementing the shaping function, the shaper, is also part of the high speed adapter cards and controls the sending of the output traffic cells.
FIG. 2 shows a network node 5 which shall include shaper and policer functions. Reference numeral 15 designates the input lines conveying the input cell streams which are received by the input adapters 10; in each adapter the policer controls and penalizes, if necessary, the cell stream for each user. Then the cells are switched in the switch 30 and sent to the output adapters 20. In each output adapter 20 there is a shaper which spaces the cells which are sent to the output lines 25 as illustrated in FIG. 1.
FIG. 3 shows an example of network topology to convey the traffic of users from the source unit 40 to the destination unit 60 through the networks 42 and 52. In these networks the nodes 45 are the access nodes; the policers are implemented in these access nodes 45. The shapers are implemented in the source unit 40 and in the node 50 which is at the boundary of the first network 42 and which accesses the second network 52. As the destination unit 60 may be a Customer Premise Node having implemented a policer, it is recommended to implement also a shaper in the node 55 located at the boundary of the network 52.
Many policing schemes have recently been studied; some of the most known are the leaky bucket, the jumping window, the moving window as described by Raif O. Onvural in his book entitled "Asynchronous Transfer Mode Networks: performance issues", Artech House edition. Without lack of generality, each policing function estimates one or more traffic parameters for a given period of time P. As this period of time P decreases, the policer may become non-transparent to users generating a traffic in conformance with the parameters negotiated at connection establishment time. On the other hand, as P increases, the policer takes longer to detect that the source exceeds its declared characteristics. However, the latter approach is more fair since it allows the user to generate a stream of cells that have short-term fluctuations. This is done at the expense of more memory requirements at the node level.
The only policing function proposed as a standard by the ITU (International Telecommunications Union), is the Generic Cell Rate Algorithm (GCRA). Details of the GCRA are given in the ATM Forum, "ATM User-Network Interface Specification", Version 3.0, 1994. Its role is, for each connection, to monitor the traffic arriving upstream according to the cell period T (T corresponds to the inverse of the peak cell rate R) and a given tolerance {character pullout} on this period. Basically, a cell is assumed to be conforming if the time elapsed between the arrival of two consecutive cells (belonging to the same connection) is greater than or equal to T-{character pullout}. If not, the cell is assumed to be non-conforming and is tagged and then, possibly discarded.
The policer discards cells not only because the source of traffic has violated the parameters negotiated at connection establishment but also because of a distorsion in the cell stream well known as jitter or Cell Delay Variation (CDV). This distorsion is due to the queuing of the cells at each intermediate network node and more generally the multiplexing of the cells on the output lines. The magnitude of the jitter depends on many parameters: the connection peak rate, the peak rate of the other connections that share the same link, the link load, the number of nodes passed through etc . . . . A consequence of the jitter is to induce, as the user cells travel through the network, some distortion on the traffic parameters declared by the source upstream. Especially, the instantaneous peak cell rate R' which may be modified and may pass beyond the value R declared by the source upstream at connection establishment time. In the worst case R'&gt;R and the policing function with a short measurement interval (small period of time P) may take undesirable discarding actions. This is typically the case of the GCRA when the specified tolerance {character pullout}, named Cell Delay Variation Tolerance (CDVT), is small. That's why the shaping function will buffer cells so that the departure rate from a node is less that the arrival rate. It has been shown that the multiplexing of spaced cells tends to decrease the "burstiness" of the aggregate traffic and then allows a better utilization of the network resources. Policing and shaping control techniques should take into account the real-time constraints; as implemented in high speed network node adapters dealing with lines at several hundreds of Megabits per second. For example, the cell transmission time (cell time cycle) is about 2.7 .mu.s for a line speed of 155.52 Mbps (OC-3), and less than 0.7 .mu.s for a line speed of 622.08 Mbps (OC-12). This implies that the shaping and policing methods have a very short time to `manage` an incoming call. For instance, assuming that only ten instructions are needed to both compute a cell transmission time and queue the cell to an output buffer; assuming that each instruction takes no more than one time cycle, the execution requires from the processor more than 14 Mips (Million of instructions per second) devoted to this task, for an OC-12 output link. Usually hardware devices are preferred and only simple computations (a few software instructions) and basic manipulations of cells are possible. As a consequence, shaping function will have to cope with a trade-off between complexity and performance and any step or device slowing-down the shaping process shall represent a serious drawback to the operability of the network.
Taking into account these above performance considerations, two shaping schemes are briefly examined hereunder.
The first one, relies on a very basic principle: the shaping function sends a given number, p, of cells at the link speed C, and keeps "silent" (i.e. the cells are buffered) till p(C/R-1).
If this approach requires no computation nor complex operations at the cell level, the CDV induced is quite bad and the tolerance that should be accommodated at the GRCA level to accept all the cells would be typically p(C/R-1).
The second one, more sophisticated, is detailed in Eugen Wallmeier and Tom Worster's article entitled "The spacing Policer, an algorithm for efficient peak bit rate control in ATM networks", published in the Proceedings of the of the XIV International Switching Symposium, Yokohama, Japan, Oct. 25-30, 1992. For an incoming cell of one connection, the time between two cell transmissions is such that the output peak rate is met, and the cell is queued to a list-of-cells that have to be sent at the same time tk. This list is referenced by the nth entry of a cyclic calendar with N inputs. A new entry of the calendar is sought at each cell time cycle, and the list-of-cells that have to be sent at time tn (0.ltoreq.n&lt;N) if any, is moved and queued to an output list. In short, the following operations are done at each cell time cycle:
Computing the transmission time ti for the incoming cell belonging to connection i PA1 Enqueueing the cell to the list-of-cells at the nth (0.ltoreq.n&lt;N) entry of the calendar. PA1 Moving the list-of-cells of the current position m (0.ltoreq.m&lt;N) of the calendar to the output list. PA1 Sending the first cell to the output list. PA1 Incrementing the calendar position. PA1 splitting said calendars into so-called pages with n cells entries per page, n being a predefined number; PA1 providing and associating to said calendars a Free Location Table organized into n-bits wide pages wherein each bit position in a page is associated to a cell entry position in the corresponding calendar page, said Free Location Table bit position being set either to 0 or to 1 depending on whether the corresponding calendar cell position is free or busy in the corresponding calendar page; whereby said calendar updating includes: for each new entry, locating the theoretical entry position in the standby calendar, defining the corresponding page, reading the corresponding Free Location Table page and should said Free Location Table page contain only ones, detecting a collision situation in which case the system looks for the nearest Free Location Table page including at least one free bit position, then performing an entry in the nearest free position of corresponding standby calendar page and updating the Free Location Table and the calendar accordingly; and, PA1 Swapping said active and standby calendars.
As one can see, the number of computations/manipulations is important. Moreover, the size of the calendar has to be quite large to support connections with small peak rate (large T). Although this algorithm gives good results in terms of CDV, it is impossible (without the knowledge of the aggregate incoming traffic pattern) to predict the jitter induced by the spacer. Therefore, the tolerance that should be accommodated at the GCRA must be quite large to ensure a minimal cell loss probability.
Most of the existing shaping schemes rely on the following principle: they compute a cell transmission time at each cell arrival, which depends on both current time and the time when the last cell was transmitted. For this reason, these shaping schemes may be referred to as cell-basis schemes. This is both time consuming and implying a heavy computing load.
A first improved method was proposed in the Copending European Application Number 94480086.1 to the same assignee. Said method is based on scheduling in advance the departure time of data cells provided by the network sources. The shaping is activated each time a change occurs in the traffic supported : new traffic added, end of traffic, modification in the traffic already established.
To that end, the proposed method consists in preparing in advance the departure of the cells for all the traffic established in the network node and which will be sent onto the output lines. For each output line, the cell stream is stored into two lookup tables called the calendars: the active calendar and the standby calendar.
While improving condiderably the traffic shaping, said method may, and does, lead to so-called colliding situations which affect the system performances.
One object of the present invention is to provide an improved method for shaping data cells transfers while minimizing the collision situations and therefore improving the system performances.
Another object of the present invention is to provide a hardware apparatus for implementing the method of this invention.
Still another object of the invention is to provide a mechanism allowing a fast resolution of the collisions detected during the write entries of an ATM shaping table.
These and other objects, characteristics and advantages of the invention, shall be more readily apparent from the following description of a preferred embodiment made with reference to the accompanying drawings.